package es.ull.etsii.aa.metodos;

import java.util.Collections;
import java.util.LinkedList;
import java.util.Random;

import es.ull.etsii.aa.datos.Nodo;
import es.ull.etsii.aa.datos.Problema;
import es.ull.etsii.aa.datos.SolucionTTRP;

public class VNS {

	private Problema problema;

	/**
	 * Constructor.
	 * 
	 * @param problema
	 *            Datos del problema a resolver.
	 */
	public VNS(Problema problema) {
		this.problema = problema;
	}

	/**
	 * Mejora una solucion dada mediante un procedimiento de busqueda en entorno
	 * variable.
	 * 
	 * @param solucion
	 *            Solucion a mejorar.
	 * @param limite
	 *            Limite de intensidad de las perturbaciones.
	 * @return Solucion mejorada.
	 */
	public SolucionTTRP mejorarSolucion(SolucionTTRP solucion, int limite) {
		SolucionTTRP mejor = solucion;
		BL bl = new BL(problema);
		RFCS rfcs = new RFCS(problema);

		boolean betterFound;

		do {
			betterFound = false;
			int k = 1;

			do {
				LinkedList<Nodo> tour = (LinkedList<Nodo>) mejor.getTour();
				tour = perturbar(tour, k);

				SolucionTTRP aux = rfcs.evaluar(tour);
				//System.out.println("busqueda local " + aux);
				aux = bl.busquedaLocal(aux);

				if (aux.compareTo(mejor) < 0) {
					mejor = aux;

					betterFound = true;
					k = 1;
				} else {
					k++;
				}

			} while (k <= limite);

		} while (betterFound);

		return mejor;
	}

	/**
	 * Perturba la representacion de una solucion.
	 * 
	 * @param tour
	 *            Representacion inicial de la solucion.
	 * @param k
	 *            Intensidad de la perturbacion.
	 * @return Representacion perturbada.
	 */
	private LinkedList<Nodo> perturbar(LinkedList<Nodo> tour, int k) {
		LinkedList<Nodo> tourMod = new LinkedList<Nodo>(tour.subList(1,
				tour.size() - 1));
		Random rng = new Random(System.nanoTime());

		for (int i = 0; i < k; i++) {
			int indice1 = rng.nextInt(tourMod.size()), indice2;

			do {
				indice2 = rng.nextInt(tourMod.size());
			} while (indice1 == indice2);

			Collections.swap(tourMod, indice1, indice2);
		}

		tourMod.addFirst(tour.getFirst());
		tourMod.addLast(tour.getFirst());

		return tourMod;
	}
}
